package com.practice.dp;

import java.util.ArrayList;

/**
 * When scheduling tasks to be executed by a person, it is sometimes the case
 * that when one task is completed, a later task suddenly becomes more
 * important. In these situations, it is said that the later task is a
 * 'Supertask' of the completed one. 
 * 
 * In addition, when a task reaches a certain level of importance, it must be 
 * executed immediately. Each task is initially given a priority of 0. Whenever 
 * a task is completed, the priority of its Supertask increases by 1. If at some 
 * moment one of the tasks has a priority of 2, and has not been previously 
 * executed, it must be executed immediately. If no remaining task has a priority 
 * of 2, a single unexecuted task of your choice must be executed (you can not 
 * wait and must execute one of them). 
 * 
 * You have been given N tasks (referenced by numbers 0 to N-1) that must be 
 * executed. All of these tasks (with the exception of the last) have a single
 * Supertask, and you are guaranteed that the reference number of a task will
 * always be lower than the reference number of its Supertask. The last task has
 * no supertask, instead the number -1 is used. You also wish to execute the
 * last task (with reference number N-1) as late as possible. Every task takes
 * one minute to complete execution. Given the supertasks for each task, return
 * the latest time (in minutes) that the last task can be started, if you start
 * executing tasks at time 0. You will be given the supertasks as a int[]
 * supertasks, where element i of supertasks contains the reference number of
 * the supertask for task i.
 */
public class PendingTasks {
	public int latestProcess(int[] supertasks) {
		int N = supertasks.length;
		if (N == 1)
			return 0;

		int[] full = new int[N];
		int[] trigger = new int[N];
		int[] safe = new int[N];
		ArrayList<Integer>[] lists = new ArrayList[N];

		for (int i = 0; i < N; i++) {
			lists[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < N - 1; i++) {
			lists[supertasks[i]].add(i);
			full[i]++;
			full[supertasks[i]] += full[i];
		}

		for (int i = 0; i < N; i++) {
			for (int j : lists[i]) {
				int count = 0;
				for (int k : lists[i]) {
					count += j == k ? full[j] : safe[k];
				}
				safe[i] = Math.max(safe[i], count);
			}
		}

		for (int i = 0; i < N; i++) {
			trigger[i] = 1;
			for (int j : lists[i]) {
				for (int k : lists[i]) {
					int count = 1;
					for (int l : lists[i]) {
						if (l == j)
							count += full[l];
						else if (l == k)
							count += trigger[l];
						else
							count += safe[l];
					}
					trigger[i] = Math.max(trigger[i], count);
				}
			}
		}

		return trigger[N - 1] - 1;
	}
}
